1. Technical Field of the Invention
The present invention relates in general to the digital processing field and, in particular, to a method for measuring system clock signal frequency variations in digital processing systems.
2. Description of Related Art
A typical method used to assess the quality of a system clock in a digital processing system is to continuously monitor the frequency of the system clock signal over a pertinent period of time. Specifically, the basic approach followed with this method is to continuously measure variations in the clock signal frequency (i.e., frequency wander or drift). Essentially, the less the clock signal frequency wanders or drifts during the measurement period, the higher the clock signal quality.
U.S. Pat. No. 5,319,583 discloses one or more methods for measuring system clock signal quality which are currently being used. A sliding window minimum or maximum filter with a window length, n, is used to convert a series of input data values into a series of output data values. Each output value is the minimum (or maximum) of the current input value and the nxe2x88x921 preceding input values. As such, this method is used to measure the minimum (or maximum) clock signal frequencies.
A digital data signal buffer is used, which is large enough to store the resulting xe2x80x9cnxe2x80x9d minimum (or maximum) measured signal values within the length (time interval, T) of the sliding window. The filter produces, for each input signal, an output signal which is the minimum or maximum of all the values within the buffer up to the most recent input signal value. The buffer is updated each signal measurement period, (T/n), such that each time a new signal measurement value is stored in the buffer, the oldest value is deleted. Consequently, it becomes necessary to perform a search to re-compute the output signal. As such, every time a new signal is stored in the buffer, the output signal has to be re-computed. Consequently, the buffer update time can become quite excessive. Therefore, it is desirable to minimize the update time.
According to U.S. Pat. No. 5,319,583, the solution disclosed has an average (buffer) update or search time which is independent from both the length of the buffer used to store the incoming signal values and the resolution of the stored data. However, for the worst case scenario using such a solution, the number of elements that can be searched is n/3, where n is the number of elements within the sliding window. In other words, the size of the sliding window determines the computation (and output signal re-computation) time, and for the worst case scenario, this value (n/3) can be quite large. Notwithstanding the solutions disclosed in U.S. Pat. No. 5,319,583, the basic problem that still needs to be resolved is to determine just how to improve clock signal frequency measurement performance by reducing the search or computation time and the number of operations required to perform the clock signal frequency minimum (or maximum) measurements in real-time. Nevertheless, as described in detail below, the present invention successfully resolves the above-described problems and other related problems.
In accordance with a preferred embodiment of the present invention, a method for measuring system clock signal frequency variations is provided, whereby the number of search operations can be limited to log2n, where n is the number of elements (containing signal values) within the sliding window used. For this embodiment, a binary search tree is used to sort the minimum value. A condition imposed for the binary tree is that the signal values contained in both the children elements are greater than or equal to the signal value contained in the parent element. As such, each element of the binary tree contains a signal value, and a flag indicating which of the two children elements contains the smallest signal value. The element at the root of the tree contains the smallest signal value for the entire tree. Whenever a new signal value for an element is retrieved, the new signal value replaces the oldest signal value in the tree. The element containing the oldest signal value can be located anywhere in the tree.
An important technical advantage of the present invention is that a method is provided for minimizing the number of operations required to compute a minimum value for a sliding window minimum filter even if the sliding window contains a relatively large number of elements.
Another important technical advantage of the present invention is that a method is provided for minimizing the response time for a sliding window minimum filter.
Still another important technical advantage of the present invention is that a method is provided for improving the performance of a sliding window minimum filter.
Yet another important technical advantage of the present invention is that a method is provided for improving the performance of system clock signal frequency measurements.